import math
class Solution:
    def countPrimes(self, n: int) -> int:
        def judge(val):
            for i in range(2,int(math.sqrt(val))):
                if val%i==0:
                    return False
            return True
        isprimes=[0 for i in range(n)]
        count=0
        for i in range(2,n):
            if isprimes[i]==0:
                count+=1
                j=i
                while i*j<n:
                    isprimes[i*j]=1
                    j+=1
        return count

s=Solution()
print(s.countPrimes(100))


'''
执行用时：
1012 ms
, 在所有 Python3 提交中击败了
25.04%
的用户
内存消耗：
35.3 MB
, 在所有 Python3 提交中击败了
40.43%
的用户

埃氏筛
'''